Perfect graph Totally Explained

Everything about Perfect Graph totally explained

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. That is, if every complete subgraph has at most k vertices, the graph can be colored with k colors, and this same relation between complete subgraphs and coloring holds in every induced subgraph of the graph.
   In any graph, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring. The perfect graphs are those for which this lower bound is tight, not just in the graph itself but in all of its induced subgraphs. For more general graphs, the chromatic number and clique number can differ; for example, a cycle of length 5 requires three colors in any proper coloring but its largest clique has size 2.
   Perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time . In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs.
   The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the complement of a bipartite graph is perfect; this result can also be viewed as a simple equivalent of König's theorem, a much earlier result relating matchings and vertex covers in bipartite graphs. The first use of the phrase "perfect graph" appears to be in a 1963 paper of Claude Berge. In this paper he unified Gallai's result with several similar results by defining perfect graphs and conjecturing a characterization of these graphs that was later proven as the Strong Perfect Graph Theorem.

Families of graphs that are perfect

Some of the more well-known perfect graphs are

bipartite graphs
The line graphs of bipartite graphs (see König's theorem)
interval graphs (vertices represent line intervals; and edges, their pairwise nonempty intersections)
chordal graphs (every cycle of four or more vertices has a chord, which is an edge between two nodes that are not adjacent in the cycle)
comparability graphs (a vertex per element in a partial order, and an edge between any two comparable elements)
wheel graphs with an odd number of vertices
Meyniel graphs (every cycle of odd length at least 5 has at least 2 chords)
split graphs (graphs which can be partitioned into a clique and an independent set)
strongly perfect graphs (every induced subgraph has an independent set intersecting all its maximal cliques)
distance-hereditary graphs

Characterizations and the perfect graph theorems

Characterization of perfect graphs has been known to be difficult. The first breakthrough was the affirmative answer to the then perfect graph conjecture. Perfect Graph Theorem. (Lovász 1972) ť A graph is perfect if and only if its complement is perfect.

An induced cycle of odd length at least 5 is called an odd hole. An induced subgraph that's the complement of an odd hole is called an odd antihole. A graph that doesn't contain any odd holes or odd antiholes is called a Berge graph. By virtue of the perfect graph theorem, a perfect graph is necessarily a Berge graph. But it puzzled people for a long time whether the converse was true. This was known as the strong perfect graph conjecture and was finally answered in the affirmative in May, 2002. Strong Perfect Graph Theorem. (Chudnovsky, Robertson, Seymour, Thomas 2002) ť A graph is perfect if and only if it's a Berge graph.

As with many results discovered through structural methods, the theorem's proof is long and technical. Efforts towards solving the problem have led to deep insights in the field of structural graph theory, where many related problems remain open. For example, it was proved some time ago that the problem of recognizing Berge graphs is in co-NP (Lovász 1983), but it wasn't known whether or not it's in P until after the proof of the Strong Perfect Graph Theorem appeared. (A polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković shortly afterwards, independent of the Strong Perfect Graph Theorem.)

Related classes of graphs

strongly perfect ť :every induced subgraph H has an independent set meeting all maximal cliques of H.

trivially perfect ť :for every induced subgraph H, the size of the largest independent set of H equals the number of maximal cliques of H

very strongly perfect ť :for every induced subgraph H, every vertex of H belongs to an independent set of H meeting all maximal cliques of H.

Further Information

Get more info on 'Perfect Graph'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://perfect_graph.totallyexplained.com">Perfect graph Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.